# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/1/2 18:48
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : rational_function_approximation.py
@Version     : Version 1.0.0
@Description : TODO 自己实现有理逼近，帕德逼近,Stein算法
@Created By  : PyCharm
"""


def gcd_core(a: int, b: int):
    if a == 0:
        return b
    if b == 0:
        return a
    while a & 0x1 == 0:
        a >>= 1
    if a < b:
        b = (b - a) >> 1
        return gcd_core(b, a)
    else:
        a = (a - b) >> 1
        return gcd_core(a, b)


def gcd(a: int, b: int):
    """
    stein算法实现求a,b整数的最大公约数
    :param a: 整数a
    :param b: 整数b
    :return: 最大公约数
    """
    c = 0
    while a & 0x1 == 0 and b & 0x1 == 0:
        a >>= 1
        b >>= 1
        c += 1
    if a & 0x1 == 0:
        a >>= 1
        return gcd_core(a, b) << c
    else:
        return gcd_core(b, a) << c


if __name__ == '__main__':
    print(gcd(1024,64))
